package main

import (
	"container/list"
	"strconv"
	"strings"
)

func l394DecodeString(s string) string {
	type stack struct {
		res string
		k   int
	}
	repeat := func(k int, s string) string {
		var ss = ""
		for k > 0 {
			ss += s
			k--
		}
		return ss
	}

	store := list.New()
	var res = ""
	var k = 0
	for _, c := range s {
		if string(c) == "[" {
			store.PushBack(&stack{res: res, k: k})
			res = ""
			k = 0
		} else if string(c) == "]" {
			sis := store.Back().Value.(*stack)
			store.Remove(store.Back())
			res = sis.res + repeat(sis.k, res)
		} else if c >= 48 && c <= 57 {
			nk, _ := strconv.Atoi(string(c))
			k = k*10 + nk
		} else {
			res += string(c)
		}
	}

	return res
}

func betterDecodeString(s string) string {
	loop := func(str string, k string) string {
		intK, _ := strconv.Atoi(k)
		res := ""
		for i := 0; i < intK; i++ {
			res += str
		}
		return res
	}

	if !strings.Contains(s, "[") {
		return s
	}

	tmpK, tmpStr, ans, stack := "", "", "", 0
	for i := 0; i < len(s); i++ {
		if stack == 0 && s[i] >= 48 && s[i] <= 57 {
			tmpK += string(s[i])
		} else if string(s[i]) == "[" {
			stack++
			if stack == 1 {
				continue
			}
		} else if string(s[i]) == "]" {
			stack--
			if stack == 0 {
				ans += loop(betterDecodeString(tmpStr), tmpK)
				tmpK, tmpStr = "", ""
			}
		} else if stack == 0 {
			ans += string(s[i])
		}

		if stack > 0 {
			tmpStr += string(s[i])
		}
	}

	return ans
}

// 作者：luhua
// 链接：https://leetcode-cn.com/problems/decode-string/solution/go-di-gui-by-luhua/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
